Leetcode-Dynamic Programming

Longest Palindromic Substring

回文字符串:正读反读都一样

方法一:暴力法

遍历所有的子字符串,判断它是不是回文字符串

class Solution {
    public String longestPalindrome(String s) {
        if(s.length()==1){
            return s;
        }
        if(s.isEmpty()){
            return "";
        }
        int maxn=0;
        int iMin=0;
        //遍历每个子字符串并判断是不是回文的
        for(int i=0;i<s.length();i++){
            for(int j=s.length()-1;j>=i;j--)
                if(s.charAt(i)==s.charAt(j)){
                    if(check(s,i,j)){
                        if(j-i+1>maxn){
                            maxn=j-i+1;
                            iMin=i;
                        }
                        break;
                    }
                }
        }
        return s.substring(iMin,maxn); 
    }
    //检测一个字符串是不是回文  
    public boolean check(String s,int i,int j){
        while(i<=j){
            if(s.charAt(i)!=s.charAt(j)){
                return false;
            }
            i++;
            j--;
        }
        return true;
    }
}

算法分析:
时间复杂度O(n^3)

方法二:动态规划

暴力法时间复杂度高的原因是去检查每一个子字符串是不是回文的,降低时间复杂度就要减少对子字符串是不是回文的判断

假设一个字符串”ababa”,当我已经确认了”bab”是回文字符串,由于它左右两边的字符都是a,那么这个完整的字符串本身就是回文的,就可以不用对整个字符串再进行完整的判断。

假设一个字符串的长度为n,那么建立一个n*n数组P。在矩阵中P[i][j]=l,若l>0:表示以字符S[i]开始和以S[j]结尾的字符串是回文字符串,字符串的长度为l;若l=0,表示此字符串不是回文字符串  
只需要对矩阵中j>=i的部分赋值即可,就j<i部分为0;
    1.一个字符的情况:将矩阵的对角线赋值为1,因为每个字符本身是回文的  
    2.两个字符的情况:j-i=1
        P[i][j]=2,if S[i]=S[j]
    3.多个字符的情况:j-i>=2
        if S[i]!=S[j] 
            P[i][j]=0;
        if S[i]=S[j]
            if P[i+1][j-1]>0
                P[i][j]=p[i+1][j-1]+2;
            else
                P[i][j]=0;
    字符串有多个字符组成时,如果两边的字符相等,那么这个字符串可能是回文的,这时将字符串去掉首末字符得到子字符串,如果子字符串回文的,那么这个字符串也是回文的。
public static String longestPalindrome(String s){
    if(s.length()==0){
        return "";
    }
    if(s.length()==1){
        return s;
    }
    int[][] p=new int[s.length()][s.length()];
    int indexMin=0,maxn=1;
    //初始化二维数组P
    for(int i=0;i<s.length();i++){
        for(int j=0;j<s.length();j++){
            if(i==j) p[i][j]=1;
        }
    }
    for(int j=0;j<s.length();j++){
        for(int i=j-1;i>=0;i--){
            if(s.charAt(i)==s.charAt(j)){
                if(j-i==1){
                    p[i][j]=2;
                }
                if(j-i>=2){
                    if(p[i+1][j-1]>0){
                        p[i][j]=p[i+1][j-1]+2;
                    }else{
                        p[i][j]=0;
                    }
                }
            }else{
                p[i][j]=0;
            }
            if(p[i][j]>maxn){
                maxn=p[i][j];
                indexMin=i;
            }
        }
    }
    return s.substring(indexMin, indexMin+maxn);
}

算法分析:
时间复杂度:O(n^2)
空间复杂度:O(n^2),需要一个n*n的矩阵来存储数据

方法三:Expand Around Center

对于动态规划算法时间复杂度为O(n^2),空间复杂度为O(n^2),可以进一步优化只用O(1)的空间实现O(n^2)的时间复杂度

一个回文字符串它是成中心对称的,比如”baab”,”bab”,但是回文字符串分为两种:奇数字符数,偶数字符数

class Solution {
    public String longestPalindrome(String s) {
        if(s.length()==0){
            return "";
        }
        if(s.length()==1){
            return s;
        }
        int indexMin=0,maxn=1;
        for(int i=0;i<s.length();i++){
            int len1=expandAroundCenter(s,i,i);
            int len2=expandAroundCenter(s,i,i+1);
            int len=Math.max(len1,len2);
            if(len>maxn){
                indexMin=i-(len-1)/2;
                maxn=len;
            }
        }
        return s.substring(indexMin,indexMin+maxn);
    }
    private int expandAroundCenter(String s,int L,int R){
        while(L>=0 && R<s.length() && s.charAt(L)==s.charAt(R)){
            L--;
            R++;
        }
        return R-L-1;
    }      
}  

算法分析
时间复杂度:O(n^2)
空间复杂苏:O(1)

方法四:最长公共字符串**

将字符串S翻转为S’,检查S和S’的最长公共字符串就是S的最长回文子字符串
此方法中存在一种问题,就是当字符串中某一个子串存在一个镜像子串本身并不是回文的,翻转之后会被检测为回文的。

下面是一种基于动态规划的求解最长公共字符串的方法。

Longest Common Substring 最长公共子字符串

动态规划问题

问题:因为有重叠子问题,当前计算的过程中可能有的问题在之前的计算已经计算过了,现在又要计算一遍,导致大量重复的计算 

动态规划的解决方法:动态规划通过找到解决问题的递推关系,将已经完成计算的存储起来,当开始新的计算时如果包含之前计算的子问题时,不需要再次计算,只需要访问已经存储的计算结果就可以

动态规划解决问题的方法一般减少了时间复杂度,增加了存储空间。

动态规划问题的两个特点:

  1. 最优子结构
  2. 重叠子问题
对于这个问题,假设有两个字符串s[0,...m],t[0,...,n],求两个字符串的最长公共子字符串    
定义矩阵mXn的矩阵L,L[i][j]表示以s[i]开始和t[j]结尾的公共子字符串长度的最大值,那么对于L[i+1][j+1]只是比L[i][j]增加了s[i+1]和t[j+1]
因此可以构造出最长公共子字符串的递归式:
    if s[i]==t[j]
        L[i][j]=L[i-1][j-1]+1
    if s[i]!=t[j]
        L[i][j]=0  

假设有两个字符串:”ABAB”和”BABA” ,构造出了上述的矩阵

代码实现

public static String LCS(String s1,String s2){
    if(s1.isEmpty() || s2.isEmpty()){
        return "";
    }
    int indexMax=0,maxn=0;
    int[][] L=new int[s1.length()][s2.length()];
    for(int i=0;i<s1.length();i++){
        for(int j=0;j<s2.length();j++){
            if(s1.charAt(i)==s2.charAt(j)){
                if(i==0 || j==0){
                    L[i][j]=1;
                }else{
                    L[i][j]=L[i-1][j-1]+1;
                }
            }
            if(L[i][j]>maxn){
                maxn=L[i][j];
                indexMax=i;
            }
        }
    }
    return s1.substring(indexMax+1-maxn, indexMax+1);
}

算法分析:
时间复杂度:O(mn)
空间复杂度:O(m
n)

算法优化
从上面动态查找最长公共子字符串的过程中发现,在循环查找的过程中只会用到矩阵L中的两行,即正在计算的一行和完成计算的上一行,之前计算的和带计算的都用不到,所以只需要维护两行数据就足够了,不需要使用mxn的数组

代码实现:

public class LCS_improve {
    public static String LCS_improve(String s1,String s2){
        if(s1.isEmpty() || s2.isEmpty()){
            return "";
        }
        int indexMax=0,maxn=0;
        int [][] L=new int[2][s1.length()];
        for(int i=0;i<s1.length();i++){
            int cur=(i+2)%2;
            int pre=(i+1)%2;
            for(int j=0;j<s2.length();j++){
                if(s1.charAt(i)==s2.charAt(j)){
                    if(i==0 || j==0){
                        L[cur][j]=1;
                    }else{
                        L[cur][j]=L[pre][j-1]+1;
                    }
                }else{
                    L[cur][j]=0;
                }
                if(L[cur][j]>maxn){
                    maxn=L[cur][j];
                    indexMax=i;
                }
            }
        }
        return s1.substring(indexMax+1-maxn, indexMax+1);
    }
}

算法分析:
时间复杂度:O(mn)
空间复杂度:O(min(m,n))